package com.zlk.algorithm.algorithm.dynamicPlan;

import java.util.HashSet;
import java.util.PriorityQueue;

// 丑数 II
// 给你一个整数 n ，请你找出并返回第 n 个 丑数
// 丑数 就是只包含质因数 2、3 或 5 的正整数
// 测试链接 : https://leetcode.cn/problems/ugly-number-ii/
public class Code05_UglyNumberII {

    public static void main(String[] args) {
        nthUglyNumber(10);
    }


    /**
     * 优先队列方法   后面的丑数肯定是前面的丑数*2 *3 或者*5
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(n)
     * @param n
     * @return
     */
    public static int nthUglyNumberMySelf(int n) {
        PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
        int ans = -1;
        priorityQueue.add(1L);
        HashSet<Long> sets = new HashSet<>();
        sets.add(1L);
        int[] arr = new int[]{2,3,5};
        for (int i = 0; i <n ; i++) {
            long cur= priorityQueue.poll();
            ans = (int)cur;
            for (int fac : arr) {
                if(sets.add(fac*cur)){
                    priorityQueue.add(fac*cur);
                }
            }
        }
        return ans;
    }


    /**
     * 动态规划
     * @param n
     * @return
     */
    public static int nthUglyNumber(int n) {
        // dp 0 1 2 ...  n
        //      1 2 ...  ?
        int[] dp = new int[n + 1];
        dp[1] = 1;
        //后面的丑数肯定是前面的丑数*2 *3 或者*5
        //维护三个指针
        //开始位置在1 所以有三个指针都指向 1位置
        //   然后取最小的 2， 此时1位置的2指针就不需要了（应为1已经乘过2了，不会再乘2 了），
        //   2指针直接转移到 2上面，形成了单调性。  3、5指针还在1 位置
        //  核心思想和上述优先队列其实是一致的，只不过优先队列的内部排序是logn
        //     1              2           3
        //  2  3  5           2
        //
        for (int i = 2, i2 = 1, i3 = 1, i5 = 1, a, b, c, cur; i <= n; i++) {
            a = dp[i2] * 2;//2
            b = dp[i3] * 3;//3
            c = dp[i5] * 5;//5
            cur = Math.min(Math.min(a, b), c);
            if (cur == a) {
                i2++;//2
            }
            if (cur == b) {
                i3++;
            }
            if (cur == c) {
                i5++;
            }
            dp[i] = cur;
        }
        return dp[n];
    }




}
